Ransom note

Time: O(N); Space: O(1); easy

Given an arbitrary ransom note string and another string containing letters from all the magazines,

write a function that will return True if the ransom note can be constructed from the magazines; otherwise, it will return False.

Each letter in the magazine string can only be used once in your ransom note.

Example 1:

Input: ransomNote = “a”, magazine = “b”

Output: False

Example 2:

Input: ransomNote = “aa”, magazine = “ab”

Output: False

Example 3:

Input: ransomNote = “aa”, magazine = “aab”

Output: True

Notes: * You may assume that both strings contain only lowercase letters.

[1]:

class Solution1(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        counts = [0] * 26
        letters = 0

        for c in ransomNote:
            if counts[ord(c) - ord('a')] == 0:
                letters += 1
            counts[ord(c) - ord('a')] += 1

        for c in magazine:
            counts[ord(c) - ord('a')] -= 1
            if counts[ord(c) - ord('a')] == 0:
                letters -= 1
                if letters == 0:
                    break

        return letters == 0

[2]:

s = Solution1()

ransomNote = "a"
magazine = "b"
assert s.canConstruct(ransomNote, magazine) == False

ransomNote = "aa"
magazine = "ab"
assert s.canConstruct(ransomNote, magazine) == False

ransomNote = "aa"
magazine = "aab"
assert s.canConstruct(ransomNote, magazine) == True

[3]:

import collections

class Solution2(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        return not collections.Counter(ransomNote) - collections.Counter(magazine)

[4]:

s = Solution2()

ransomNote = "a"
magazine = "b"
assert s.canConstruct(ransomNote, magazine) == False

ransomNote = "aa"
magazine = "ab"
assert s.canConstruct(ransomNote, magazine) == False

ransomNote = "aa"
magazine = "aab"
assert s.canConstruct(ransomNote, magazine) == True